package com.zjb.datastructure.stack;

public class StackTree {
    public static void main(String[] args) {
        int[] tree = {0, 18, 12, 15, 10, 8, 13, 14, 7};

        //大顶堆

        //int[] bigTree = new int[15];

        int[] insert = insert(6, tree);

        removeTop(insert);

        for (int i = 0; i < insert.length; i++) {
            System.out.print(insert[i] + "\t");
        }
        removeTop(insert);
        System.out.println();
        for (int i = 0; i < insert.length; i++) {
            System.out.print(insert[i] + "\t");
        }


    }

    static int[] insert(int data, int[] tree) {
        int newLength = tree.length + 1;
        int[] bigTree = new int[newLength];
        System.arraycopy(tree, 0, bigTree, 0, tree.length);
        bigTree[newLength - 1] = data;

        newLength--;

        while (newLength / 2 > 0 && bigTree[newLength / 2] < bigTree[newLength]) {
            int top = newLength / 2;
            int temp = bigTree[newLength];
            bigTree[newLength] = bigTree[top];
            bigTree[top] = temp;

            newLength = top;

        }
        return bigTree;


    }


    static int[] removeTop(int[] tree) {

        tree[1] = tree[tree.length - 1];

        tree[tree.length - 1] = 0;

        recurive(tree, 1);

        return tree;
    }

    static void recurive(int[] tree, int index) {

        int left = index * 2, rignt = index * 2 + 1;
        if (left > tree.length || rignt > tree.length) {
            return;
        }
        if (tree[left] > tree[rignt] && tree[left] > tree[index]) {
            swap(tree, left, index);
            recurive(tree,left);
        } else if (tree[rignt] > tree[left] && tree[rignt] > tree[index]) {
            swap(tree, rignt, index);
            recurive(tree,rignt);
        }

    }

    static void swap(int[] tree, int src,int target) {
        int temp = tree[src];
        tree[src] = tree[target];
        tree[target] = temp;
    }

}
